#include <iostream>

using namespace std;

void LCSLength(int m, int n, string x, string y, int c[100][100], char b[100][100]) {

    int i, j;
    for (i = 0; i <= m; i++) c[i][0] = 0;
    for (j = 0; j <= n; j++) c[0][j] = 0;
    for (i = 1; i <= m; i++)
        for (j = 1; j <= n; j++)
            if (x[i - 1] == y[j - 1]) {
                c[i][j] = c[i - 1][j - 1] + 1;
                b[i][j] = '%';
            } else if (c[i - 1][j] >= c[i][j - 1]) {
                c[i][j] = c[i - 1][j];
                b[i][j] = '^';
            } else {
                c[i][j] = c[i][j - 1];
                b[i][j] = '<';
            }
}

void LCS(int i, int j, string x, char b[100][100]) {
    if ((i == 0) || (j == 0)) return;
    if (b[i][j] == '%') {
        LCS(i - 1, j - 1, x, b);
        cout << x[i - 1];
    } else if (b[i][j] == '^') LCS(i - 1, j, x, b);
    else LCS(i, j - 1, x, b);
}

int main() {


    string x = "ABCBDAB";
    string y = "BDCABA";
//    string x,y;
//    cin>>x;
//    cin>>y;
//    vector<vector<int> > c(x.length()+1, vector<int>(y.length()+1, 0));
//    vector<vector<char> > b(x.length()+1, vector<char>(y.length()+1, 0));
    int c[100][100];
    char b[100][100];

    LCSLength(x.length(), y.length(), x, y, c, b);
    for (int i = 0; i < x.length() + 1; ++i) {
        for (int j = 0; j < y.length() + 1; ++j) {
            cout << c[i][j] << " ";
        }
        cout << endl;
    }
    for (int i = 0; i < x.length() + 1; ++i) {
        for (int j = 0; j < y.length() + 1; ++j) {
            cout << b[i][j] << " ";
        }
        cout << endl;
    }
    LCS(x.length(), y.length(), x, b);
}